package com.my.code.consistenthash;

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * <b>一致性Hash的实现</b><p>
 * 使用TreeMap实现一致性hash <p>
 * 泛型S 封装了机器节点的信息，如name，password，ip，port
 * 实际情况还要考虑到真实节点的新增和下线
 *
 * @author zzl
 * @date 2020/10/26
 */
public class Shard<S extends Node> {
    private static final int NODE_NUM = 10;//每个真实节点对应虚拟节点个数，实际环境需要支持配置
    private TreeMap<Long, S> nodes;//虚拟节点
    private List<S> shards;//真实机器节点

    public Shard(List<S> shards) {
        this.shards = shards;
        init();
    }

    /**
     * 初始化一致性hash环
     */
    private void init() {
        nodes = new TreeMap<>();
        for (S s : shards) {
            for (int i = 0; i < NODE_NUM; i++) {

                nodes.put(hash(getSrcKey(s, i)), s);
            }
        }
    }

    /**
     * 根据key获取真实节点信息
     *
     * @param key 用来路由的key，这里的key可使用业务上的key，可以使用用户的ip和port，不需要知道服务真实和虚拟节点信息
     */
    public S getShard(String key) {
        SortedMap<Long, S> tail = nodes.tailMap(hash(key));// 沿环的顺时针找到一个虚拟节点
        if (tail.size() == 0) return nodes.get(nodes.firstKey());
        return tail.get(tail.firstKey());
    }

    /**
     * 添加真实节点，未考虑线程同步的情况
     *
     * @param s 要添加的节点信息
     */
    public boolean addShard(S s) {
        for (int i = 0; i < NODE_NUM; i++) {
            nodes.put(hash(getSrcKey(s, i)), s);
        }
        return shards.add(s);
    }

    //实际hash的key可能会根据ip和port来计算，这里简单的使用序号
    private String getSrcKey(S s, int vnodeIndex) {
        return "SHARD-" + s.getIndex() + "-NODE-" + vnodeIndex;
    }

    /**
     * 移除真实节点，未考虑线程同步的情况
     *
     * @param s 要移除的节点信息
     */
    public boolean removeShard(S s) {
        for (int i = 0; i < NODE_NUM; i++) {
            nodes.remove(hash(getSrcKey(s, i)));
        }
        return shards.remove(s);
    }

    /**
     * MurMurHash算法，是非加密HASH算法，性能很高，注意它计算结果是包含负值的情况
     * 比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）等HASH算法要快很多，而且据说这个算法的碰撞率很低.
     * http://murmurhash.googlepages.com/
     * 常见的hash算法有 CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法
     */
    private Long hash(String key) {

        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;

        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);

        long m = 0xc6a4a7935bd1e995L;
        int r = 47;

        long h = seed ^ (buf.remaining() * m);

        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }

        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
            // for big-endian version, do this first:
            // finish.position(8-buf.remaining());
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        buf.order(byteOrder);
        return h;
    }

}
